package com.example.algorithm.linkedlist;

public class Leetcode203 {

    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        if (head == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = pre.next;
        while (cur != null) {
            if (cur.val == val) {
                ListNode delNode = cur;
                pre.next = cur = cur.next;
                delNode.next = null;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 添加一个虚拟头结点
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        while (pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }
        return dummyHead.next;
    }

    /**
     * 使用递归的方式实现
     * @param head
     * @param e
     * @return
     */
    public ListNode removeElementRecursive(ListNode head, int e) {
        if (head == null) {
            return head;
        }
        ListNode res = removeElementRecursive(head.next, e);
        if (head.val == e) {
            return res;
        } else {
            head.next = res;
            return head;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 6, 3, 4, 5, 6};
        ListNode head = new ListNode(nums);
        System.out.println(head.toString());
        ListNode listNode = new Leetcode203().removeElements(head, 6);
        System.out.println(listNode);

        System.out.println();

        ListNode head2 = new ListNode(nums);
        System.out.println(head2);
        ListNode listNode2 = new Leetcode203().removeElements2(head2, 6);
        System.out.println(listNode2);

        System.out.println();

        ListNode head3 = new ListNode(nums);
        System.out.println(head3);
        ListNode listNode3 = new Leetcode203().removeElementRecursive(head3, 6);
        System.out.println(listNode3);
    }

}
